class Solution {
public:
    int findroot(vector<int>& ufs,int i){
        while(ufs[i] >= 0){
            i = ufs[i];
        }
        return i;
    }
    bool equationsPossible(vector<string>& equations) {
        vector<int> ufs(26,-1);
        for(int i = 0;i < equations.size();i++){
            if(equations[i][1] == '='){
                int root1 = findroot(ufs,equations[i][0] - 'a');
                int root2 = findroot(ufs,equations[i][3] - 'a');
                if(root1 != root2){
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            } 
        }
        for(int i = 0;i < equations.size();i++){
            if(equations[i][1] == '!'){
                int root1 = findroot(ufs,equations[i][0] - 'a');
                int root2 = findroot(ufs,equations[i][3] - 'a');
               if(root1 == root2) return false;
            } 
        }
        return true;
    }
};
